package leetcode;

import java.util.Arrays;
import java.util.Set;
import java.util.TreeSet;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2021-10-18 08:59
 **/
public class LeetCode414 {

    /**
     * 我想到的简单解法，排序:时间复杂度(O(nlog(n))(看了官方题解优化过的代码)
     * @param nums
     * @return
     */
    /*public int thirdMax(int[] nums) {
        Arrays.sort(nums);
        for (int n = nums.length - 1, count = 1; n > 0; n--) {
            if (nums[n] != nums[n - 1] && ++count == 3) {
                return nums[n - 1];
            }
        }
        return nums[nums.length - 1];

    }*/

    /**
     * 看了官方题解-有序集合写的解法
     * @param nums
     * @return
     */
    /*public int thirdMax(int[] nums) {
        TreeSet<Integer> treeSet = new TreeSet<Integer>();
        for (int num : nums) {
            treeSet.add(num);
            if (treeSet.size() > 3) {
                treeSet.remove(treeSet.first());
            }
        }
        return treeSet.size() == 3 ? treeSet.first() : treeSet.last();

    }*/

    /**
     * 一次遍历的方法
     * @param nums
     * @return
     */
    public int thirdMax(int[] nums) {
        long a = Long.MIN_VALUE;
        long b = Long.MIN_VALUE;
        long c = Long.MIN_VALUE;
        for (int num : nums) {
            if (a < num) {
                c = b;
                b = a;
                a = num;
            } else if (a > num && num > b) {
                c = b;
                b = num;
            } else if (b > num && num > c) {
                c = num;
            }
        }
        return c == Long.MIN_VALUE ? (int)a : (int) c;
    }

    public static void main(String[] args) {
        LeetCode414 code = new LeetCode414();
        code.thirdMax(new int[]{1, 2, 2, 5, 3, 5});
    }

}
